public class BaseList<T> implements LinearList<T> {

	private T head;
	private BaseList<T> tail;

	public BaseList() {
		this(null, null);
	}

	public BaseList(T elem, BaseList<T> bl) {
		this.head = elem;
		this.tail = bl;
	}
	
	public LinearList<T> add(T elem) {
		if(elem==null){
			throw new NullPointerException("Cannot add NULL element.");
		}
		return new BaseList<T>(elem,this);
	}

	public boolean contains(T elem) {
		BaseList<T> current=this;
		while(!current.isEmpty()){
			if(current.head.equals(elem)){
				return true;
			}
			current=current.tail;
		}
		return false;
	}

	public T getHead() {
		return head;
	}

	public LinearList<T> getTail() {
		return tail;
	}

	public boolean isEmpty() {
		return this.head==null;
	}

	public LinearList<T> remove(T elem) {
		BaseList<T> current=this;
		
		if(head!=null && head.equals(elem)){
			return tail;
		}
		while( !current.isEmpty() ){
			if(!current.next().isEmpty()&&current.next().head.equals(elem)){
				current.tail=next().tail;
				return this;
			}
			current=current.next();
		}
		return null;
	}

	private BaseList<T> next(){
		return tail;
	}
	
	public int size() {
		int i=0;
		BaseList<T> current=this;
		while(current.head!=null){
			current=current.next();
			if(current==null){
				return i;
			}
			i++;
		}
		return i;
	}

	public int count(Condition<T> c){		
		if(iAmLast()){
			if(c.evaluate(head)){
				return 1;
			}
			return 0;
		}
		
		if(c.evaluate(head)){
			return next().count(c)+1;
		}
		return next().count(c);
	}
	
	public LinearList<T> filter(Condition<T> c){		
		if(iAmLast()){
			if(c.evaluate(head)){
				return this;
			}
			return new BaseList<T>();
		}
		
		if(c.evaluate(head)){
			return next().filter(c).add(this.head);
		}
		return next().filter(c);
	}
	
	public <S> LinearList<S> map(Function<T,S> f){		
		if(iAmLast()){
			return new BaseList<S>().add(f.evaluate(head));
		}
		
		LinearList<S> ans=next().map(f);
		return ans.add(f.evaluate(head));
	}
	
	private boolean iAmLast(){
		return next()==null;
	}
	
	public <S> LinearList<S> inject(Function<T,S> f,S init){		
		S myVal=f.evaluate(head,init);
		
		if(iAmLast()){
			return new BaseList<S>(myVal,null);
		}
		return (next().inject(f,myVal)).add(myVal);
	}
		

	public LinearList<T> invert(){
		return invert(0);
	}
	
	private LinearList<T> invert(int i){		
		BaseList<T> next=this.tail;
		int size=size();
		
		if(size==1){
			return this;
		}
		if(size==2){
			next.tail=this;
			return next;
		}
		
		if(i==0){
			LinearList<T> newHead=next.invert(i+1);
			tail=null;
			return newHead;
		}
		else{
			LinearList<T> newHead=next.invert(i+1);
			next.tail=this;
			return newHead;
		}
	}
		
}
